Speaker: Eva Maria Feichtner Date: November 2003

Topics: Mathematics, lectures

Speaker: Jeorg Rambau Date: July 2003

Topics: Mathematics, Lectures

Speaker: Joerg Rambau Date: July 2003

Topics: Mathematics, Lectures

Speaker : Greg Sorkin Keywords : Analysis of algorithms; average-case analysis; branching processes; Brownian motion; phase transition; scaling window; constraint satisfaction; satisfiability. Abstract : A maximum cut in a random graph below the giant component threshold can be found in linear space and linear expected time by a simple algorithm. The same algorithm solves the more general class Max 2-CSP of weighted binary 2-variable constraint satisfaction problems, which includes weighted Max...

Topics: Mathematics, lecture

Speaker: Nikolai Makarov Date: 05/01/01

Topics: Mathematics, lectures

Speaker: Nina Amenta Date: August 2003

Topics: Mathematics, Lectures

Speaker: Imre Barany Date: August 2003

Topics: Mathematics, Lectures

Speaker : Dave Bayer

Topics: Mathematics, lecture

Speaker : Dave Bayer

( 2 reviews )

Topics: Mathematics, lecture

Speaker: Robert K. Lazarsfeld Date: September 2002

Topics: Mathematics, lectures

Speaker: Robert K. Lazarsfeld Date: September 2002

Topics: Mathematics, lectures

Speaker: Robert K Lazarsfeld Date: September 2002

Topics: Mathematics, Lectures

Speaker : Mark Ward Keywords : Analysis of algorithms; data compression; suffix trees; tries; Poissonization; Mellin transform; redundancy; pattern matching. Abstract : We present the asympotics of the distribution and moments of Mn, the matching multiplicity parameter, for tries constructed on independent strings. We also present work-in-progress that Mn for suffix trees has the same asympotic distribution and moments.

Topics: Mathematics, lecture

Speaker : Philippe Jacquet

Topics: Mathematics, lecture

Speaker : Vincent Puyhaubert Keywords : Analysis of algorithms; analytic urns, stable limit law, Mellin transform, Fubini theorem, Event generating function, Convergence in distribution Abstract : We present an analytic approach to urn models. The method is the same as in Flajolet-Gabarro-Pekari wich consists in enumerating all events starting from an initial urn. A PDE is obtained for the generating function wich is solved by method of characteristics. Then the analytic study of the GF derives...

Topics: Mathematics, lecture

Speaker: Jonathan Shewchuk Date: October, 2003

( 1 reviews )

Topics: Mathematics, lectures

Speaker: Jeffrey Lagarias Date: November, 2003

Topics: Mathematics, lectures

Speaker : Chuck Knessl Keywords : Analysis of algorithms; Asympotics; WKB method; digital trees; quicksort; binary search trees; matched asympotic expansions. Abstract : We apply singular perturbation techniques to the analysis of algorithms and to trees. Examples include digital tress, binary search trees and quicksort algorithm.

Topics: Mathematics, lecture

Speaker : Bob Gomph

Topics: Mathematics, lecture

Speaker : Mortiz Maass Keywords : Analysis of algorithms; approximate pattern matching; tries; average-case analysis; humming distance; indexing. Abstract : We analyze the asympotic average -case behavior of a search process in random tries. A pattern is searched in a set of strings under a certain pair-based error function. Error functions are possible. We find different asympotic behavior dependent on the error probability and the number of mismatches allowed.

Topics: Mathematics, lecture

Speaker: David Mount Date: October, 2003

Topics: Mathematics, lectures

Speaker: Timothy Chan Date: October, 2003

Topics: Mathematics, lectures

Speaker : William P. Thurston

Topics: Mathematics, lecture

Speaker : William P. Thurston

Topics: Mathematics, lecture

Speaker: Vladlen Koltun Date: October, 2003

Topics: Mathematics, lectures